package it.storm.solution;

import java.util.Arrays;

/**
 * 31. 下一个排列
 * https://leetcode-cn.com/problems/next-permutation/
 */
public class Solutions_31 {
    public static void main(String[] args) {
//        int[] nums = {1, 2, 3};  // output: {1, 3, 2}
//        int[] nums = {3, 2, 1};  // output: {1, 2, 3}
//        int[] nums = {2, 1};  // output: {1, 2}
//        int[] nums = {1, 1, 5};  // output: {1, 5, 1}
//        int[] nums = {1, 5, 5};  // output: {5, 1, 5}
        int[] nums = {4, 2, 0, 2, 3, 2, 0};  // output: {4, 2, 0, 3, 0, 2, 2}

        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void nextPermutation(int[] nums) {
        int len = nums.length;
        // 1.倒序遍历，从倒数第 2 个元素遍历，对于每一个索引 i，查找区间 [i + 1, nums.lenght - 1] 中的元素
        // 判断区间内是否存在大于 nums[i] 的元素，若有，说明可以组成下一个更大的排列
        for (int i = len - 2; i >= 0; i--) {
            for (int j = len - 1; j > i; j--) {
                if (nums[j] > nums[i]) {
                    // 2.数值交换
                    int temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                    // 3.[j, nums.length - 1] 部分，升序排列
                    // 为什么直接翻转 [i + 1, len - 1] 区间的元素，也能实现排序？因为 [i + 1，len - 1] 区间的元素一定是递减的
//                    Arrays.sort(nums, i + 1, len);
                    swap(nums, i + 1, len - 1);
                    // 交换并排序后，此时的 nums 数字，就是下一个更大的排列了
                    return;
                }
            }
        }
        // 4.不存在下一个更大的排列，将数字重新排列成最小的排列
        Arrays.sort(nums);
    }

    public static void swap(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left ++;
            right --;
        }
    }
}
